The Viterbi algorithm (VA) is well known as an efficient maximum likelihood (ML) sequence estimator of data encoded by a finite state machine and corrupted by white noise. See, G. D. Forney Jr., "The Viterbi Algorithm," Proc. IEEE, vol. 61, no. 3, pp. 268-278, Mar. 1973. In many applications, the output of the Viterbi decoder is further processed by a second decoder in a concatenated coding system. FIG. 1 shows a concatenated coding system in which outer encoder 121 transforms an information sequence a(k) into sequence b(k). Inner encoder 123 further encodes sequence b(k) to produce a sequence to be transmitted. Inner decoder 125 decodes the received sequence r(k) to produce an estimate b(k) of the sequence encoded by inner encoder 123. Outer decoder 127 then uses b(k) to generate an estimate a(k) of the information sequence. Table 1 lists four examples of specific coder combinations typical for the concatenated system of FIG. 1. In all of these, the optimal decoder should operate on the joint state space of the outer and the inner code to obtain an estimate of the information sequence. However, in the first coding combination, i.e. the combined speech and channel coding scheme, of Table 1, it is not yet known how to describe such a decoder. In the other three cases, such a decoder may be too complex to implement especially when powerful codes are used for inner and outer codes. Hence a practical approach is to first perform the decoding of the received data by the inner decoder followed by outer decoding.
TABLE 1 ______________________________________ Outer Inner Inner Outer Encoder Encoder Decoder Decoder ______________________________________ 1. Speech Encoder Convolutional Viterbi Speech Encoder Decoder Decoder 2. Error Detection Convolutional Viterbi Syndrome Encoder Encoder Decoder Decoder 3. Convolutional ISI Channel Viterbi Viterbi Encoder Channel Equalizer Decoder 4. Reed-Solomon Convolutional Viterbi Errors and Encoder Encoder Decoder Erasures Decoder ______________________________________
Typically, the inner decoder produces burst errors. If the outer code is a random error correcting code, then an interleaver/deinterleaver pair 222,226 as illustrated in FIG. 2 may be inserted in the coding system of FIG. 1. The pair will help to pseudo-randomize the burst of errors so as to facilitate the outer decoding process. If the outer code/interleaver/inner code combination is thought of as a new code, then its optimal decoder, which requires exhaustive search, is even more difficult to implement.
Several techniques have been developed to improve the performance of concatenated coding systems. One such technique is the generalized Viterbi algorithm (GVA). See T. Hashimoto, "A List-Type Reduced-Constraint Generalization of the Viterbi Algorithm," IEEE Trans. Inf. Theory, IT-33, pp. 866-876, Nov. 1987; N. Seshadri and C-E. W. Sundberg, "Generalized Viterbi Algorithms for Error Detection With Convolutional Codes," in Proc. GLOBECOM'89, Dallas, Tex., pp. 1534-1538, Nov. 1989. The GVA generates a list of the L&gt;1 best estimates (also called candidate sequences) of b(k) at the inner decoder output according to a metric that describes the inner channel. Each of these candidate sequences is decoded by the outer decoder according to a metric that best describes the outer channel. The best of the L decoded candidate sequences is selected as the final estimate of the information sequence. For example, in a combined speech and channel coding system of Table 1, the metric for decoding the outer code may make use of speech based properties such as pitch information, spectral information, and inter-frame correlation in order to select the of the L candidate sequences from the inner decoder. In the second case in Table 1, the outer decoder chooses the candidate with zero syndrome from the L best candidate sequences that are released by the inner decoder. See Seshadri and Sundberg, supra.
Alternatively, soft (symbol)-output Viterbi algorithms (SOVAs) have been proposed to replace the VA at the inner decoding stage. See G. Battail, "Weighting the Symbols Decoded by the Viterbi Algorithm," Abstracts of the IEEE Int. Symp. Inf. Theory, Ann Arbor, Mich., p. 141, Oct. 1986; J. Hagenauer and P. Hoeher, "A Viterbi Algorithm With Soft-Decision Outputs and its Applications," Proc. GLOBECOM'89, Dallas, Tex., pp. 1680-1686, Nov. 1989; J. Huber and Rueppel, "Reliability-Estimation for Symbols Detected by Trellis-Decoders," (in German), AEU, vol. 44, pp. 8-21, Jan. 1990. In the SOVA, the inner decoder releases the best path estimate at the output of the inner decoder along with the reliability information about each symbol in the sequence decoded by the inner decoder. The outer decoder then uses the reliability information in soft-decoding the output sequence of the inner decoder. Maximum a posteriori symbol-by-symbol detection techniques (also known as optimal symbol-by-symbol detection techniques) can also be used. However, their complexity is much higher than soft-output Viterbi algorithms.
The soft-output techniques for post-decision reliability generation suffer from shortcomings. First, the best data sequence clearly passes through only one state in the Viterbi decoding trellis at every time instant, and these decisions are available with a certain delay. Hence, if one introduces a delay in computing the soft-outputs, then the decoded symbols are available and the reliability needs to be computed only for those symbols. However, the SOVA evaluates a reliability value at the same time as the data is being decoded and thus has to compute a reliability value for each state at each time. "Two step algorithms" are more computationally efficient, but their drawback is the amount of memory required--typically, about 50% of the area of an integrated circuit designed to implement the method is consumed by the additional delay units needed to store metric differences. See J. Hagenauer, P. Hoeher, and J. Huber, "Soft-Output Viterbi and Symbol-by-Symbol MAP Decoding: Algorithms and Applications," submitted to IEEE Trans. Comm.: O. Jorgensen, M. Vaupel, and H. Meyr, "High-Speed VLSI Architectures for Soft-Output Viterbi Decoding," Proc. Int. Conf. Appl. Specific Array Processors (ASAP'92), Berkeley, Aug. 1992. Second, whenever the inner decoder makes an error the errored sequence is likely to be from a small subset of all possible data sequences especially at moderate and high signal-to-noise ratios. Prior approaches make no use of this property to reduce the complexity. See G. Battail, supra; J. Hagenauer and P. Hoeher, supra; J. Huber and Rueppel, supra; J. Hagenauer, P. Hoeher, and J. Huber, supra; and O. Jorgensen, M. Vaupel, and H. Meyr, supra.
Additionally, Sfez and Battail have proposed a method which computes the ML path and the best path among alternatives in "A Weighted-Output Variant of the Viterbi Algorithm for Concatenated Schemes Using a Convolutional Inner Code," Proc. EUROCODE'90, Udine, Italy, Nov. 1990. However, this method has several disadvantages: (i) computational efforts grow exponentially with the memory in the inner coding process, which implies more complexity and memory for implementation; (ii) the technique is based on event length rather than properties of the code; and (iii) the technique is restricted to Viterbi decoding. Thus, there is a need for a method and apparatus for post-processing to provide reliability information about decoded data symbols at the output of decoders that are efficient and that may be extended beyond Viterbi decoding.